A key feature in the use of computer systems is an available memory which can provide the requisite data needed by the processing unit in the system. A special application of memory is used in many computer systems which provide a cache memory unit which is closely associated with the central processing unit (CPU) in order to provide frequently used memory data rapidly to the CPU without requiring the added delay of having to address and access the main memory unit.
The content addressable memory or CAM is a structure which uses associative memory circuits in order to do memory searches.
The conventional content addressable memory is generally constructed in very large scale integrated circuits (VLSI) by using a memory latch coupled with a comparison circuit. Such a content addressable memory (CAM) is used to perform certain basic operations such as:
(a) Write operation: where data is store individual memory addresses of the content addressable memory by a sequential writing of the data. PA1 (b) Search Operation: Where a pattern of search data is input to all of the locations in the content addressable memory and all locations are compared simultaneously in parallel with the search data. If a certain location identically "matches" the input search data, then an output signal will indicate the match condition and the "address" of the matched data which was located in the Content Addressable Memory.
The content addressable memory circuitry has many applications often in cache designs where it is desired to store recently used memory addresses in combination with the associated data that corresponds to these addresses. These associated data are stored locally near the processor in a random access memory (RAM). Thus the CAM can store a recently used data address which then can be used to point to a local memory location (in RAM) holding the associated data. When the CAM search results in a "match", then faster access to the local storage RAM is performed instead of the longer time and slower fetch period required to access the main memory.
FIG. 1A shows a typically standard content addressable memory in block diagram form. The content addressable memory CAM 200 is a latticed array composed of CAM cells 300. A diagram of the format of the conventional CAM cell 300 is shown in FIG. 2. FIG. 1B illustrates a 4.times.4 array of CAM cells forming a CAM.
Referring to FIG. 1, even though there is a multiple number of lattices of CAM cells 300 in the content addressable memory 200, for ease of explanation FIG. 1A is used to show how each one of the CAM cells is connected and operated.
The CAM cell 300 (as one example of the many CAM cells involved) is provided with a word line 202 which carries an address. As seen in FIG. 1B, there is a word address line 202.sub.a- 202.sub.d for each row of CAM cells (which carry a data word). Also the CAM cell 300 has a match "hit" line 204 which exits through a first output 205 in FIG. 1A.
Likewise in FIG. 1B, a set of hit lines 204a-204d exits from each row of CAM cells. The search key/data-in is a set of digital input lines in FIG. 1A and represented by line 222, FIG. 1A, and which are applied, after splitting, by means of inversion, into bit line 206 and bit line 208, FIG. 1A, to provide an input to the CAM 300 (and all of the other CAM cells involved) in a given row. In FIG. 1B these inputs are shown as D1, D2, D3, D4.
The "search" is initiated by an activator signal on line 220, FIGS. 1A, 1B, through the OR gate 228 which also has an input from the Write activating signal 218, FIG. 1B.
The Read signal on line 216 FIG. 1A is used to activate Transistors Td.sub.1 and Td.sub.2 in order to enable the sense amplifier 224 to output data on line 226. The Read activating line 216, FIG. 1A, is also seen to feed into OR gate 214 whose output is then sent as one input to the AND gate 212. The address decoder 210 provides address data input into AND gate 212 which provides for selection of the word line 202.
The OR gate 228, FIG. 1A, receives inputs from the Write line 218 and from the Search activating line 220 such that only one of these lines 218 and 220 will activate the output of the OR gate 228.
The Search activating line 220, FIG. 1A, when operative through the OR gate 228 will activate the transistors Ts.sub.1 and Ts.sub.2 so that the search key data may enter on the data-in line 222 and be conveyed on the bit lines 206 and 208 up to the CAM cell 300.
FIG. 1B is a more detailed view of FIG. 1A in order to indicate how line 202 of FIG. 1A is really a group of word lines 202.sub.a, 202.sub.b, 202.sub.c, 202.sub.d, in FIG. 1B. Likewise the Data In/Search Key line 222 of FIG. 1A is actually a set of multiple lines D.sub.1, D.sub.2, D.sub.3, D.sub.4 of FIG. 1B.
The conventional CAM block diagram of FIG. 1A is expressed only in schematic form since there are a multiplicity of the CAM cells 300 and there is also a multiplicity of input address lines, data input/search key lines and also a multiplicity of data output lines. Thus with reference to FIG. 1B, there is indicated a more realistic representation of a conventional content addressable memory or CAM.
As seen in FIG. 1B, there is provided an array of CAM cells such that the first row of CAM cells are designated C11, C12, C13, and C14. This represents the cell positioning in row 1 and the sequence in the CAM array to show which numbered position in the cell rests.
Likewise the second row of CAM cells is designated C21, C22, C23, C24 which last unit represents the CAM cell in the second row and in the fourth column.
In FIG. 1B, there are a series of word address line inputs designated 202.sub.a, 202.sub.b, 202.sub.c, and 202.sub.d. Each of these lines is an address input which can access one row of CAM cells. Thus if line 202.sub.b is being activated, it will access the CAM cells C21, C22, C23, C24 which represents 4 bits of data holding a 4 bit word.
Likewise in FIG. 1B there are seen a set of "match" lines designated 204.sub.a, 204.sub.b, 204.sub.c, and 204.sub.d. Each of these lines is an output line which represents the first word in the first row, the second word in the second row, the third word in the third row, and the fourth word in the fourth row such that when one of these match lines is activated, it indicates that the particular data bit word (4 bit word) in that particular row has been matched by input search-key data which has been applied to the input lines D.sub.1, D.sub.2, D.sub.3, and D.sub.4. Thus if the input lines D.sub.1 through D.sub.4 should represent the bits 1001, and if the same data of 1001 is also residing in the second row of CAM cells (C21 through C24) then there is a match or "hit" which is accomplished so that the output line 204.sub.b will be activated and will convey a signal to the logic unit L.sub.i which will tell the logic unit which particular address was found to contain the data that matched the input lines D.sub.1, D.sub.2, D.sub.3, and D.sub.4.
With reference to FIG. 1B, there is seen a Read line 216 which is used to activate a set of 4 groups of transistors designated R1a, R1b, R2a, R2b, R3a, R3b, and R4a, R4b. These transistors are activated by the Read line 216 so that if an address for the word line 202.sub.c is activated, then residing in cells C.sub.31, C.sub.32, C.sub.33, C.sub.34 will be transmitted through the sense Amplifiers A.sub.1, A.sub.2, A.sub.3, A.sub.4 to the Data Out lines DO1, DO2, DO3 and DO4.
Referring to FIG. 1B, it is seen that each "column" of CAM cells will have a "pair" of output lines (which pass through the Read line transistors R.sub.1 a, R.sub.1 b) for example, which connect to the output lines 206.sub.a1 and 206.sub.b1 which are the output lines for the first column of CAM cells. Then for example if the address line 202.sub.b activates the second row of CAM cells, then the data in these 4 CAM cells (C21, C22, C23, C24) will be passed down through their Read output lines 206.sub.a1 and 206.sub.b1 ; 206.sub.a2, and 206 .sub.b2 ; 206.sub.a3, and 206.sub.b3 ; and 206.sub.a4 and 206.sub.b4.
Due to the activation of the transistors R1a,b R2a,b R3a,b and R4a,b the output data signals will pass through the sense amplifiers A1, A2, A3, A4 in order to provide the data out signal on lines DO1, DO2, DO3, DO4.
The chief operating function of the content addressable memory (CAM) is the ability to search the data in the various rows of words, which in this example of FIG. 1B shows that there are 4 rows of words and each word has a content of 4 bits. Thus using the search-key input lines D1, D2, D3, and D4 and enabling the transistors SW for each of the columns, the bit data on lines D1 through D4 will be transmitted up through each column of the series of data words in the content addressable memory 200. Then, for example, if the input data on lines D1 through D4 should be the digital number 0110 and if it was found that the data in the third row of CAM cells matched this, that is to say the data in that row was 0110, then the match or hit line 204.sub.c would be activated in order to send a signal to the logic L.sub.1 which would indicate that the address residing in the third word line, that is to say, row 3 of CAM cells C31 through C34, is the address being read out on lines DO1 through DO4.
In the above illustration of FIG. 1B, it can be seen on the timing diagram of FIG. 3, that it would take 1 clock period to insert the search-key data, and a second clock period in order to do the matching for the output "match" lines. Likewise in order to Write data into a given location it would first be necessary to establish the address in the address word lines using 1 clock time and then to use a second clock time in order to write in the data by means of input lines D1, D2, D3, and D4.
It also may be noted in the timing of FIG. 3 that when a word line WL is activated by the address, for example, as the activation of line 202.sub.b (which activates the second row of data forming a 4 bit word), it is possible to simultaneously activate the Read line 216, but however the output data on lines DO1, DO2, DO3, DO4, would not become forthcoming until the subsequent clock time had expired so that it would take at least 2 clocks for this to occur.
It would be most desirable for conditions to be such that the search and match operations could be accomplished in one clock time and also that the read and data out operations could be accomplished in one clock time thus insuring a faster and quicker set of operations for the access of data or for the writing in of data or for the searching of data to be read out.
This improved condition can be realized by the architecture of the CAM system described hereinafter.
The "standard type" of CAM cell 300 is seen in FIG. 2 as being composed of transistors having certain functions. The area of transistors marked TC is the conventional flip-flop set of transistors in which one pair of transistors involves the "set mode" while the other pair of transistors involves the "reset mode". The area marked C1 involves 2 transistors which provide the conventional compare operation for the "reset mode" while the area marked C2 provides for 2 transistors which provide the conventional compare operation for the "set mode".
Again as seen in FIG. 2, the bit lines 206 and 208 are the input/output lines for the reading-in and writing-out of data. The word line address line WL is designated as 202 in order to provide an output address while the match line 204 is the hit line which is output as 205.
Now referring to FIG. 3, the timing operation for a Search and for a Read of the content addressable memory, CAM, (shown in FIGS. 1A and 2) will be observed. The first line of FIG. 3 shows the clock signal with the first clock being designated as T1 and the second clock being designated as T2. The activity of the Search-key occurs in the area of the first clock with a slight overlap into the second clock. The execution of the "match" operation occurs toward the end of the first clock mainly into the second clock.
For a "Read" operation the word line address on line 202 (FIG. 1A) is seen to function shortly after the beginning of the second clock in that the read lines signal activation occurs shortly after the initiation of the second clock. It will be noted that the Data-Out on line 226 of FIG. 1A does not occur till the end portion of the second clock and on outward into the third clock. Thus it is seen that more than 2 clock periods are necessary in order to provide the functions of search-compare, match ("hit") operation; and then the action of the word line address with Read activation and Data readout, then takes additional clock time.
Thus in the standard applications for a content addressable memory, operation requires that there first be a search compare operation to see if a particular data word exists in the CAM. And then there is the need to read the contents of the CAM, (assuming that a hit or match has occurred), resulting in a second operation for read out of the word which requires an additional system clock.
As will be noted in FIGS. 1A and 2, the operation of the Search-key/Data-in, on line 222, the Data-Out on line 226 are seen to use the same bit lines (206, 208) for the inputs and outputs. Because of this, the operations of (i) data in; (ii) data out or (iii) Search key cannot occur simultaneously during the same clock cycle.
Thus in the operations of the standard conventional CAM 101 regarding a selected memory location, as seen in FIG. 4, the Search key data is sent through the bit lines (106, 108) to be compared with the contents of a selected address. If the Search key data in matches the contents of a selected address, this results in a match or hit signal coming out through line 104 of FIG. 4, comparable to output 205 on line 204, FIG. 1.
If the contents of the CAM do not match the Search-key data then the contents of the selected, address of memory is read to the "Data-out" line 126 of FIG. 4 (comparable to 226 of FIG. 1A) for further evaluation.
As will be seen with reference to FIG. 3 in the timing diagram, the Search-Compare and Read operations together require at least 2 clock cycles to complete. In a 16 megahertz system, this would involve a "time loss" of 62.5 nanoseconds.
An object of the present disclosure is to obviate the extended time-loss period and eliminate need for multiple clock cycles in accomplishing the Search-compare and data Read actions. The present system will be seen to permit the execution of a Search-Compare-Read operation in the very same cycle.